package com.nanbei.backyracking;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ClassDescription: 回溯算法 （N皇后） leetcode51
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/15 14:18
 */
public class NQueens {

    public static void main(String[] args) {
        System.out.println(solveNQueens(4));
    }

    public static List<List<String>> solveNQueens(int n) {
        // 记录列冲突
        boolean[] ca = new boolean[n];
        // 记录左斜线冲突 i:行 j:列  i+j
        boolean[] cb = new boolean[2*n-1];
        // 记录右斜线冲突 i:行 j:列  n-1-(i-j)
        boolean[] cc = new boolean[2*n-1];
        char[][] table = new char[n][n];
        for (char[] c : table) {
            Arrays.fill(c, '.');
        }

        // 用来保存返回的数据
        List<List<String>> count = new ArrayList<>();
        queen(0,n, ca,cb, cc,table,count);
        return count;
    }

    /**
     *  @param i 当前行
     * @param n 列 （皇后的个数）
     * @param ca 当前列的数组 默认为false  被占用则为ture
     * @param cb 左斜线
     * @param cc 右斜线
     * @param table 表
     * @param count 返回结果集和
     */
    private static void queen(int i, int n, boolean[] ca, boolean[] cb, boolean[] cc, char[][] table, List<List<String>> count) {
        if (i==n){
            ArrayList<String> objects = new ArrayList<>();
            for (char[] c : table) {
                objects.add(new String(c));
            }
            count.add(objects);
            return;
        }

        for (int j = 0; j < n; j++) {
            if (ca[j] ||cb[i+j]||cc[n-1-(i-j)]){
                continue;
            }
            ca[j] = true;
            cb[i+j] = true;
            cc[n-1-(i-j)] = true;
            table[i][j] = 'Q';
            queen(i+1, n, ca, cb, cc, table, count);
            table[i][j] = '.';
            ca[j] = false;
            cb[i+j] = false;
            cc[n-1-(i-j)] = false;

        }

    }

}
